{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reaching Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reachingPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达终点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定四个整数&nbsp;<code>sx</code>&nbsp;,&nbsp;<code>sy</code>&nbsp;，<code>tx</code>&nbsp;和&nbsp;<code>ty</code>，如果通过一系列的<strong>转换</strong>可以从起点&nbsp;<code>(sx, sy)</code>&nbsp;到达终点&nbsp;<code>(tx, ty)</code>，则返回 <code>true</code>，否则返回&nbsp;<code>false</code>。</p>\n",
    "\n",
    "<p>从点&nbsp;<code>(x, y)</code>&nbsp;可以<strong>转换</strong>到&nbsp;<code>(x, x+y)</code>&nbsp; 或者&nbsp;<code>(x+y, y)</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sx = 1, sy = 1, tx = 3, ty = 5\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:\n",
    "</strong>可以通过以下一系列<strong>转换</strong>从起点转换到终点：\n",
    "(1, 1) -&gt; (1, 2)\n",
    "(1, 2) -&gt; (3, 2)\n",
    "(3, 2) -&gt; (3, 5)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sx = 1, sy = 1, tx = 2, ty = 2 \n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sx = 1, sy = 1, tx = 1, ty = 1 \n",
    "<strong>输出:</strong> true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= sx, sy, tx, ty &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reaching-points](https://leetcode.cn/problems/reaching-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reaching-points](https://leetcode.cn/problems/reaching-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n3\\n5', '1\\n1\\n2\\n2', '1\\n1\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # 当没有任何一个维度相同的时候，缩减长的\n",
    "        while tx > sx and ty > sy:\n",
    "            # 谁长缩减谁，缩减到为tx的余数\n",
    "            if ty >= tx:\n",
    "                ty = ty % tx\n",
    "            else:\n",
    "                tx = tx % ty\n",
    "        # 退出循环的时候一定有一维<=sx <=sy，\n",
    "        # tx维度相等\n",
    "        if tx == sx and ty >= sy and (ty - sy) % sx == 0:\n",
    "            return True\n",
    "        elif ty == sy and tx >= sx and (tx - sx) % sy == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        if sx == tx:\n",
    "            return (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return (tx - sx) % ty == 0\n",
    "        return self.reachingPoints(sx, sy, tx % ty, ty) if tx > ty else self.reachingPoints(sx, sy, tx, ty % tx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        \n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while ((tx > sx) and (ty > sy) and (tx != ty)):\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx <= tx and sy <= ty:\n",
    "            if sx == tx or sy == ty:\n",
    "                if sx == tx and ty == sy: return True\n",
    "                elif sx == tx: return (ty - sy) % tx == 0\n",
    "                else: return (tx - sx) % ty == 0\n",
    "            elif tx == ty:\n",
    "                return False\n",
    "            elif tx < ty:\n",
    "                ty -= (ty - tx - 1) // tx * tx + tx\n",
    "            else:\n",
    "                tx -= (tx - ty - 1) // ty * ty + ty\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx and sy < ty:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if sx == tx and sy == ty:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        \n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx>tx or sy>ty : return False\n",
    "        if tx>ty:\n",
    "            if ty==sy:\n",
    "                return (tx-sx)%ty==0\n",
    "            else:\n",
    "                return self.reachingPoints(sx,sy,tx%ty,ty)\n",
    "        else:\n",
    "            if tx==sx:\n",
    "                return (ty-sy)%tx==0\n",
    "            else:\n",
    "                return self.reachingPoints(sx,sy,tx,ty%tx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy and tx != ty:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while (tx > sx) and (ty > sy):\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        \n",
    "        while tx > sx and ty > sy:\n",
    "            if tx == ty:\n",
    "                return False\n",
    "            elif tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "\n",
    "        if sx == tx and sy==ty:\n",
    "            return True\n",
    "        if tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        if ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy and tx != ty:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx and ty>sy and (ty-sy) % tx == 0:\n",
    "            return True\n",
    "        elif ty == sy and tx>sx and (tx-sx) % ty == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx > tx or sy > ty:\n",
    "            return False\n",
    "        if sx == tx: return (ty-sy) % tx == 0\n",
    "        elif sy == ty: return (tx-sx) % ty == 0\n",
    "\n",
    "        if tx > ty: return self.reachingPoints(sx, sy, tx%ty, ty)\n",
    "        elif tx < ty: return self.reachingPoints(sx, sy, tx,ty % tx)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "\n",
    "        if (sx > tx or sy > ty):\n",
    "            return False\n",
    "\n",
    "        while tx > sx and ty > sy:\n",
    "            tx, ty = tx % ty, ty % tx\n",
    "\n",
    "        if tx == sx and (ty - sy) % tx == 0:\n",
    "            return True\n",
    "\n",
    "        if ty == sy and (tx - sx) % ty == 0:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\r\n",
    "        while tx>=sx and ty>=sy:\r\n",
    "            if tx==sx and ty==sy:\r\n",
    "                return True\r\n",
    "            if tx==sx:\r\n",
    "                return (ty-sy)%sx==0\r\n",
    "            if ty==sy:\r\n",
    "                return (tx-sx)%sy==0\r\n",
    "            if tx>ty:\r\n",
    "                tx%=ty\r\n",
    "            else:\r\n",
    "                ty%=tx\r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx and ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        def ex(x,y):\n",
    "            return (x, y) if x<=y else (y,x)\n",
    "        # tx, ty = ex(tx, ty)\n",
    "        # if sx == tx and sy == ty: return True\n",
    "        # if sx == ty and sy == tx: return False\n",
    "        while True:\n",
    "            if ty < sy or tx < sx:\n",
    "                return False\n",
    "            if (ty==sy and tx==sx):\n",
    "                return True\n",
    "            # ty % tx 可能会跳过答案\n",
    "            if tx > ty:\n",
    "                if ty > sy: tx = tx % ty\n",
    "                elif ty == sy: return True if (tx-sx) % ty == 0 else False\n",
    "            elif tx < ty:\n",
    "                if tx > sx: ty = ty % tx\n",
    "                elif tx == sx: return True if (ty - sy) % tx == 0 else False\n",
    "            else: return False\n",
    "            # if (sy - ty % tx) % tx == 0: return True\n",
    "            # tx, ty = ty % tx, tx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx >= sx and ty >= sy:\n",
    "            if tx == sx and ty == sy:\n",
    "                return True\n",
    "        \n",
    "            if tx == ty:\n",
    "                return False\n",
    "\n",
    "            if tx >= ty:\n",
    "                if tx % ty == 0:\n",
    "                    tx = tx - max(1, min((tx // ty * ty), (tx - sx) // ty)) * ty\n",
    "                else:\n",
    "                    tx = tx - max(1, min((tx // ty - 1), (tx - sx) // ty)) * ty\n",
    "            else:\n",
    "                if ty % tx == 0:\n",
    "                    ty = ty - max(1, min((ty // tx * tx), (ty - sy) // tx)) * tx\n",
    "                else:\n",
    "                    ty = ty - max(1, min((ty // tx - 1), (ty - sy) // tx)) * tx\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        if sx == tx:\n",
    "            return (ty - sy) % sx == 0 \n",
    "        elif sy == ty:\n",
    "            return (tx - sx) % sy == 0\n",
    "        return self.reachingPoints(sx, sy, tx%ty, ty) if tx > ty else self.reachingPoints(sx, sy, tx, ty%tx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        \n",
    "        while tx > sx and ty > sy:\n",
    "            if tx > ty:\n",
    "                tx = tx%ty\n",
    "            else:\n",
    "                ty = ty%tx\n",
    "        if sx == tx and sy == ty:return True\n",
    "        elif tx == sx:\n",
    "            return False if (ty-sy) % tx or ty < sy else True\n",
    "        elif ty == sy:\n",
    "            return False if (tx-sx)%ty or tx < sx else True\n",
    "\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx>sx and ty>sy and tx!=ty:\n",
    "            if tx>ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "\n",
    "        if tx==sx and ty==sy:\n",
    "            return True\n",
    "        else:\n",
    "            if tx==ty:\n",
    "                return False\n",
    "            if tx==sx and ty>sy:\n",
    "                return (ty-sy)%tx==0\n",
    "            if ty==sy and tx>sx:\n",
    "                return (tx-sx)%ty==0\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "\n",
    "        if (sx > tx or sy > ty):\n",
    "            return False\n",
    "\n",
    "        while sx < tx and sy < ty:\n",
    "            tx, ty = tx % ty, ty % tx\n",
    "\n",
    "        if tx == sx and (ty - sy) % tx == 0:\n",
    "            return True\n",
    "\n",
    "        if ty == sy and (tx - sx) % ty == 0:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "            while tx > sx and ty > sy and tx != ty:\n",
    "                if tx > ty:\n",
    "                    tx %= ty\n",
    "                else:\n",
    "                    ty %= tx\n",
    "            if tx == sx and ty == sy:\n",
    "                return True\n",
    "            elif tx == sx:\n",
    "                return ty > sy and (ty - sy) % tx == 0\n",
    "            elif ty == sy:\n",
    "                return tx > sx and (tx - sx) % ty == 0\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while ty>sy or tx>sx:\n",
    "            if ty==sy:\n",
    "                return (tx-sx)%ty==0\n",
    "            if tx==sx:\n",
    "                return (ty-sy)%tx==0\n",
    "            if ty>=tx:\n",
    "                ty %= tx\n",
    "            elif tx>ty:\n",
    "                tx %= ty\n",
    "            if ty<sy or tx<sx:\n",
    "                return False\n",
    "        return ty==sy and tx==sx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx >= sx and ty >= sy:\n",
    "            if tx == sx and ty == sy:\n",
    "                return True\n",
    "            if tx == ty:\n",
    "                return False\n",
    "            if tx > ty:\n",
    "                k = math.ceil(tx / ty) - 1\n",
    "                p = (tx - sx) // ty\n",
    "                temp = min(k, p)\n",
    "                if temp == 0:\n",
    "                    return False\n",
    "                tx = tx -  temp * ty\n",
    "            else:\n",
    "                k = math.ceil(ty / tx) - 1\n",
    "                p = (ty - sy) // tx\n",
    "                temp = min(k, p)\n",
    "                if temp == 0:\n",
    "                    return False\n",
    "                ty = ty - temp * tx\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy:\n",
    "            tx, ty = (tx % ty, ty) if tx > ty else (tx, ty % tx)\n",
    "        return (tx == sx and ty >= sy and not (ty - sy) % sx ) or (ty == sy and tx >= sx and not(tx - sx) % sy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if(sx>sy):sx,sy,tx,ty=sy,sx,ty,tx\n",
    "        while(tx!=sx):\n",
    "            if(tx<sx or ty<sy):return False\n",
    "            tx,ty=ty%tx,tx\n",
    "        return (ty>=sy) and (ty-sy)%sx==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\r\n",
    "        if sx == tx and sy == ty:\r\n",
    "            return True\r\n",
    "        if sx > tx or sy > ty:\r\n",
    "            return False\r\n",
    "        while not(sx == tx and sy == ty):\r\n",
    "            if tx == ty or tx < sx or ty < sy:\r\n",
    "                return False\r\n",
    "            if tx > ty:\r\n",
    "                val = tx\r\n",
    "                tx %= ty\r\n",
    "                if tx < sx:\r\n",
    "                    tx += ((sx-tx)//ty)*ty\r\n",
    "                if tx == val:\r\n",
    "                    return False\r\n",
    "            else:\r\n",
    "                val = ty\r\n",
    "                ty %= tx\r\n",
    "                if ty < sy:\r\n",
    "                    ty += ((sy-ty)//tx)*tx\r\n",
    "                if ty == val:\r\n",
    "                    return False\r\n",
    "            # print(tx,ty)\r\n",
    "            if sx == tx and sy == ty:\r\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx==tx and sy==ty:\n",
    "            return True\n",
    "        while (sx<=tx and sy<=ty):\n",
    "            if tx>=ty:\n",
    "                tx%=ty\n",
    "            else:\n",
    "                ty%=tx\n",
    "            if (sx==tx) and (ty - sy) % sx==0:\n",
    "                return True\n",
    "            if (sy==ty) and (tx - sx) % sy==0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx==tx and sy==ty: return True\n",
    "        while tx != ty:\n",
    "            if tx>ty: tx -= max((tx - sx) // ty, 1) * ty\n",
    "            else: ty -= max((ty - sy) // tx, 1) * tx\n",
    "            if sx==tx and sy==ty: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy:\n",
    "            tx, ty = (tx % ty, ty) if tx > ty else (tx, ty % tx)\n",
    "        return (tx == sx and ty >= sy and not (ty - sy) % sx) or (ty == sy and tx >= sx and not(tx - sx) % sy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while ty > sy and tx > sx and ty != tx:\n",
    "            if ty > tx:\n",
    "                ty %= tx\n",
    "            else:\n",
    "                tx %= ty\n",
    "\n",
    "        if sx == tx and sy == ty:\n",
    "            return True\n",
    "        elif sx == tx and ty > sy:\n",
    "            return not (ty - sy) % sx\n",
    "        elif sy == ty and tx > sx:\n",
    "            return not (tx - sx) % sy\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # 当没有任何一个维度相同的时候，缩减长的\n",
    "        while tx > sx and ty > sy:\n",
    "            # 谁长缩减谁，缩减到为tx的余数\n",
    "            if ty >= tx:\n",
    "                ty = ty % tx\n",
    "            else:\n",
    "                tx = tx % ty\n",
    "        # 退出循环的时候一定有一维<=sx <=sy，\n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        # tx维度相等\n",
    "        return (ty - sy) % sx == 0  if tx == sx else (tx - sx) % sy == 0\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        if tx == sx:\n",
    "            return (ty - sy) % sx == 0\n",
    "        else:\n",
    "            return (tx - sx) % sy == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # 正难则反\n",
    "        # sx < tx;sy<ty;tx!=ty\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        # 判断情况\n",
    "        if sx == tx and sy == ty:\n",
    "            return True\n",
    "        elif sx == tx:\n",
    "                return ty > sy and (ty-sy)%tx == 0\n",
    "        elif sy == ty:\n",
    "                return tx > sx and  (tx-sx)%ty == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx and sy < ty:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        \n",
    "        if sx > tx or sy > ty:\n",
    "            return False\n",
    "        if sx == tx:\n",
    "            return (ty - sy) % sx == 0\n",
    "        else:\n",
    "            return (tx - sx) % sy == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx and sy < ty:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        \n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        if tx == sx:\n",
    "            return (ty - sy) % sx == 0\n",
    "        else:\n",
    "            return (tx - sx) % sy == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        \n",
    "        while tx > 0 and ty > 0:        # 因为sx, sy, tx, ty 是范围在 [1, 10^9] 的整数，逆推不能出界\n",
    "            if sx == tx and sy == ty:   # 判断是否到达了起始值\n",
    "                return True\n",
    "            \n",
    "            # 每次逆推只能有tx、ty中较大值减去较小值\n",
    "            if tx > ty:     # 此时只能有tx减去ty\n",
    "                tx -= max((tx - sx) // ty, 1)* ty\n",
    "            else:           # 此时只能有ty减去tx\n",
    "                ty -= max((ty - sy) // tx, 1) * tx\n",
    "        # end while    \n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while(sx < tx and sy < ty):\n",
    "            if (tx < ty):\n",
    "                ty = ty % tx\n",
    "            else:\n",
    "                tx = tx % ty\n",
    "            \n",
    "        if (tx < sx or ty < sy):\n",
    "            return False\n",
    "        \n",
    "        if sx == tx:\n",
    "            if ((ty-sy)%tx == 0):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            if ((tx-sx)%ty == 0):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "\n",
    "        elif tx == sx:\n",
    "            # ty 和 sy的差异可以通过不断减tx消除\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx<tx!=ty>sy:\n",
    "            if tx>ty:\n",
    "                tx%=ty\n",
    "            else:\n",
    "                ty%=tx\n",
    "        if tx==sx and ty==sy:\n",
    "            return True\n",
    "\n",
    "        elif tx==sx:\n",
    "            return ty>sy and(ty-sy)%tx==0\n",
    "        elif ty==sy:\n",
    "            return tx>sx and (tx-sx)%ty==0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while (tx > sx) and (ty > sy) and (tx != ty):\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        \n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx%=ty\n",
    "            else:\n",
    "                ty%=tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty>sy and (ty-sy)%tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx>sx and (tx-sx)%ty==0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while(sx < tx and sy < ty):\n",
    "            if (tx < ty):\n",
    "                ty = ty % tx\n",
    "            else:\n",
    "                tx = tx % ty\n",
    "            \n",
    "        if (tx < sx or ty < sy):\n",
    "            return False\n",
    "        \n",
    "        if sx == tx:\n",
    "            if ((ty-sy)%tx == 0):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            if ((tx-sx)%ty == 0):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        x,y = tx,ty \n",
    "        while x>=sx and y>=sy:\n",
    "            if x==sx and y==sy:\n",
    "                return True \n",
    "            if x==y:\n",
    "                return False\n",
    "            if x>y:\n",
    "                mx = max(y+(x-y)%y,sx+(x-sx)%y)\n",
    "                if x==mx:\n",
    "                    x = x-y\n",
    "                else:\n",
    "                    x = mx \n",
    "\n",
    "            else:\n",
    "                my = max(x+(y-x)%x,sy+(y-sy)%x)\n",
    "                if y==my:\n",
    "                    y=y-x\n",
    "                else:\n",
    "                    y = my \n",
    "\n",
    "            # print(x,y)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx==tx and sy==ty:\n",
    "            return True\n",
    "        \n",
    "        if sx>tx or sy>ty:\n",
    "            return False\n",
    "        if sx==tx:\n",
    "            return  (ty-sy)%sx==0\n",
    "        if sy==ty:\n",
    "            return (tx-sx)%sy==0\n",
    "        if tx>ty:\n",
    "            return self.reachingPoints(sx,sy,tx%ty,ty)\n",
    "        else:\n",
    "            return self.reachingPoints(sx,sy,tx,ty%tx)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # GS\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy and tx != ty:\n",
    "            if tx > ty:\n",
    "                tx = tx % ty\n",
    "            else:\n",
    "                ty = ty % tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx and ty > sy:\n",
    "            return (ty - sy) % tx == 0\n",
    "        elif ty == sy and tx > sx:\n",
    "            return (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # trace back first\n",
    "        while tx > sx and ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx < sx or ty < sy:\n",
    "            return False\n",
    "        if tx == sx:\n",
    "            return (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return (tx - sx) % ty == 0\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while tx > sx and ty > sy and tx != ty:\n",
    "            if tx > ty: \n",
    "                tx = tx % ty\n",
    "            elif tx < ty: \n",
    "                ty = ty % tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty - sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx - sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    " \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx > tx or sy > ty or sx == 0 or sy == 0: \n",
    "            return False\n",
    "        if sx == tx:\n",
    "            return (ty - sy) % sx == 0\n",
    "        if sy == ty:\n",
    "            return (tx - sx) % sy == 0\n",
    "        if tx > ty:\n",
    "            return self.reachingPoints(sx, sy, tx % ty, ty)\n",
    "        return self.reachingPoints(sx, sy, tx, ty % tx)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        while sx < tx != sy < ty:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        \n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty-sy) % tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx-sx) % ty == 0\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        # 只有 sx < tx；tx != ty； sy < ty\n",
    "        while sx < tx != ty > sy:\n",
    "            if tx > ty:\n",
    "                tx %= ty\n",
    "            else:\n",
    "                ty %= tx\n",
    "        if tx == sx and ty == sy:\n",
    "            return True\n",
    "        elif tx == sx:\n",
    "            return ty > sy and (ty-sy)%tx == 0\n",
    "        elif ty == sy:\n",
    "            return tx > sx and (tx-sx)%ty == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:\n",
    "        if sx > tx or sy > ty:\n",
    "            return False\n",
    "        if gcd(sx, sy) != gcd(tx, ty):\n",
    "            return False\n",
    "        # if tx > ty:\n",
    "        #     sx, sy, tx, ty = sy, sx, ty, tx\n",
    "\n",
    "        while True:\n",
    "            ty %= tx\n",
    "            if tx == sx:\n",
    "                return (ty - sy) % tx == 0\n",
    "            if ty < sy:\n",
    "                return False\n",
    "\n",
    "            tx %= ty\n",
    "            if ty == sy:\n",
    "                return (tx - sx) % ty == 0\n",
    "            if tx < sx:\n",
    "                return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
